﻿P8646[蓝桥杯 2017 省 AB] 包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 A
i
​
个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。
比如一共有 3 种蒸笼，分别能放 3 、 4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4 、 5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入格式
第一行包含一个整数 N。(1≤N≤100)。

以下 N 行每行包含一个整数 A
i
​
。(1≤A
    i
    ​
    ≤100)。

    输出格式
    一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。

    输入输出样例
    输入 #1复制
    2
    4
    5
    输出 #1复制
    6
    输入 #2复制
    2
    4
    6
    输出 #2复制
    INF


#include<bits/stdc++.h>
    //思路：公因数问题+dp
    //假设c为可以凑出的数；a为固定的一屉的总数；b为选几屉：那么如果可以凑出c；
    //c=a1b1+a2b2+a3b3+a4b4+...；如果能凑出c那么c一定存在；对于a系列的公共公因数可以为1
    //或者其他其他非1的数->gd;如果c可以那么c%gd一定为0；假设gd为2；c可以取到无穷；c%2可以认为有无穷个除不尽的数-->INF;因此如果输出的不是INF此时gd一定为1；
    //dp[i]表示c为i时候如果能凑成就是1；否则是0；后面可以根据决策树的方法填充dp（结论：如果gd为1；那么可以认为a（max1）*a（max2）-a(max1)-a(max2)->此题转化成max*max（包括了这个范围）【3 5与4 5】之后的所有数都可以凑成也就是之后的dp值就是1；-->填充完dp值后只需要统计前面范围内dp值为0的即可）

    using namespace std;
using ll = long long;//直接ll+大范围
vector<ll>v;
const int N = 1e5;//最大dp访问范围1e4+100
ll mx;
void solve() {
    int n;
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++)  cin >> v[i];
    ll gcd = v[0];//更新输入组的公因数
    mx = v[0];
    for (int i = 1; i < n; i++) {
        gcd = __gcd(gcd, v[i]);
        mx = max(v[i], mx);//求amx
    }
    if (gcd != 1) { cout << "INF" << endl; return; }//无穷个直接返回
    ll dp[N];
    dp[0] = 1;//b都为0
    //填充dp（指定范围）
    for (int i = 0; i <= mx * mx; i++) {
        if (dp[i] == 1) {
            for (int j = 0; j < n; j++) dp[i + v[j]] = 1;
        }
    }
    //统计不能构成的个数-->dp 0
    int ans = 0;
    for (int i = 1; i <= mx * mx; i++) {
        if (!dp[i]) ans++;
    }
    cout << ans << endl;
}
int main() {
    solve();
    return 0;
}